package com.sicheng.lc.周赛.分类.dp;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/6/15 18:32
 */
public class 检查是否有合法括号字符串路径 {
    //https://leetcode.cn/problems/check-if-there-is-a-valid-parentheses-string-path/
    int m;
    int n;
    boolean[][][] dp;

    public boolean hasValidPath(char[][] grid) {
        m = grid.length;
        n = grid[0].length;
        if (grid[0][0] == ')' || grid[m - 1][n - 1] == '(' || ((m + n - 1) & 1) == 1)
            return false;
        int p = m + n - 1 >> 1;
        dp = new boolean[m][n][p + 1];

        // 当grid(i,j) == "(" 价值是1, ")" 价值是-1
        // (0,0)->(m-1,n-1)状态必须大于等于0否则是无效路径
        //dp(i,j,k)在 坐标(i,j)位置的k转态可否取到
        // c是grid(i,j)处的价值
        //dp(i,j,k) = dp(i-1,j,k-c) | dp[i,j-1,k-c]

        dp[0][0][1] = true;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i != 0 || j != 0) {
                    int c = grid[i][j] == '(' ? 1 : -1;
                    for (int k = 0; k <= p; k++) {
                        if (k - c < 0 || k - c > p)
                            continue;

                        if (i > 0)
                            dp[i][j][k] |= dp[i - 1][j][k - c];
                        if (j > 0)
                            dp[i][j][k] |= dp[i][j - 1][k - c];

                    }
                }
            }
        }

        return dp[m - 1][n - 1][0];
    }


    public static void main(String[] args) {
        检查是否有合法括号字符串路径 solution = new 检查是否有合法括号字符串路径();
        char[][] grid = {
                {'(', '(', '('},
                {')', '(', ')'},
                {'(', '(', ')'},
                {'(', '(', ')'}
        };
        System.out.println(solution.hasValidPath(grid));
    }
}
